# Author: Yu Bin
# Date: 2025/01/02 18:48:27
# E-mail: 853823259@qq.com
# 1、完成二叉树的建树，前序，中序，后序，层序遍历
class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Binary_tree:
    def __init__(self):
        self.root = None
        self.help_queue = []

    def level_build_tree(self, node: Node):
        if self.root is None:
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    def pre_order(self, node: Node):
        if node:
            print(node.elem, end=' ')
            self.pre_order(node.lchild)
            self.pre_order(node.rchild)

    def mid_order(self, node: Node):
        if node:
            self.mid_order(node.lchild)
            print(node.elem, end=' ')
            self.mid_order(node.rchild)

    def post_order(self, node: Node):
        if node:
            self.post_order(node.lchild)
            self.post_order(node.rchild)
            print(node.elem, end=' ')

    def level_order(self):
        help_queue = [self.root]
        while help_queue:
            node = help_queue.pop(0)
            print(node.elem, end=' ')
            if node.lchild:
                help_queue.append(node.lchild)
            if node.rchild:
                help_queue.append(node.rchild)


tree = Binary_tree()
for i in range(10):
    node = Node(i)
    tree.level_build_tree(node)
tree.pre_order(tree.root)
print()
tree.mid_order(tree.root)
print()
tree.post_order(tree.root)
print()
tree.level_order()
print()
# 2、完成sorted的练习
student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
print(sorted(student_tuples, key=lambda x: x[2]))
print('-' * 100)


class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        """
        相对于__str__，可以返回非字符串类型
        :return:
        """
        return repr((self.name, self.grade, self.age))


student_objects = [
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
]
print(student_objects)
print(sorted(student_objects, key=lambda student: student.age))
print('-' * 100)

from operator import itemgetter, attrgetter

print('使用operator系列')
print(sorted(student_tuples, key=itemgetter(1)))
print(sorted(student_objects, key=attrgetter('age')))
print('使用operator系列，多列排序')
print(sorted(student_tuples, key=itemgetter(1, 2)))
print(sorted(student_objects, key=attrgetter('grade', 'age')))
print('-' * 100)
# 字典中混合 list 排序
mydict = {'Li': ['M', 7],
          'Zhang': ['E', 2],
          'Wang': ['P', 3],
          'Du': ['C', 2],
          'Ma': ['C', 9],
          'Zhe': ['H', 7]
          }
print(sorted(mydict.items(), key=lambda x: x[1][1]))
print('-' * 100)
# List 中混合字典排序
gameresult = [{"name": "Bob", "wins": 10, "losses": 3, "rating": 75.00},
              {"name": "David", "wins": 3, "losses": 5, "rating": 57.00},
              {"name": "Carol", "wins": 4, "losses": 5, "rating": 57.00},
              {"name": "Patty", "wins": 9, "losses": 3, "rating": 71.48}]
print(sorted(gameresult, key=lambda x: x['rating']))
print(sorted(gameresult, key=itemgetter("rating", "name")))
print('-' * 100)
# 难度作业：
# 3、完成快速排序，堆排序
import random


class Sort:
    def __init__(self, arr_len):
        self.arr_len = arr_len
        self.arr = [0] * arr_len
        self.random_arr()

    def random_arr(self):
        for i in range(self.arr_len):
            self.arr[i] = random.randint(0, 99)

    def partition(self, left, right):
        k = left
        for i in range(left, right):
            if self.arr[i] < self.arr[right]:
                self.arr[i], self.arr[k] = self.arr[k], self.arr[i]
                k += 1
        self.arr[k], self.arr[right] = self.arr[right], self.arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            k = self.partition(left, right)
            self.quick_sort(left, k - 1)
            self.quick_sort(k + 1, right)

    def adjust_arr(self, pos, current_len):
        son = pos * 2 + 1
        while son < current_len:
            if son + 1 < current_len and self.arr[son] < self.arr[son + 1]:
                son += 1
            if self.arr[son] > self.arr[pos]:
                self.arr[son], self.arr[pos] = self.arr[pos], self.arr[son]
                pos = son
                son = pos * 2 + 1
            else:
                break

    def heap_sort(self):
        for i in range(self.arr_len // 2 - 1, -1, -1):
            self.adjust_arr(i, self.arr_len)
        self.arr[0], self.arr[self.arr_len - 1] = self.arr[self.arr_len - 1], self.arr[0]
        for current_len in range(self.arr_len - 1, 1, -1):
            self.adjust_arr(0, current_len)
            self.arr[0], self.arr[current_len - 1] = self.arr[current_len - 1], self.arr[0]


count = 10
my_arr = Sort(count)
my_arr.quick_sort(0, count - 1)
print(my_arr.arr)
another_arr = Sort(count)
another_arr.heap_sort()
print(another_arr.arr)
